#include<iostream>
#include<vector>
#include<string>
#include<set>
using namespace std;

class Trie {
public:
	set<string> list;
	Trie() {

	}

	void insert(string word) {
		list.insert(word);
	}

	bool search(string word) {
		if (list.count(word))
			return true;
		else return false;
	}

	bool startsWith(string prefix) {
		for (string str : list) {
			if (str[0] < prefix[0]) continue;
			else if (str[0] > prefix[0]) break;
			else{
				bool flag = true;
				for (int i = 1; i < prefix.size(); i++) {
					if (str[i] != prefix[i]) {
						flag = false;
						break;
					}
				}
				if (flag) return true;
			}
		}
		return false;
	}
};

int main() {
	set<string> dict;
	dict.insert("apple");
	dict.insert("bad");
	dict.insert("app");
	dict.insert("app");
	//string a = "abc";
	//string b = "cba";
	//if (a[0] < b[0])
	//	cout << "1" << endl;
	//else cout << "2" << endl;
	Trie *t = new Trie();
	t->insert("apple");
	t->insert("app");
	bool search=t->search("app");
	bool prefix=t->startsWith("ba");
	return 0;
}